{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #String Matching in an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #string-matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #字符串匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: stringMatching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组中的字符串匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串数组 <code>words</code> ，数组中的每个字符串都可以看作是一个单词。请你按 <strong>任意</strong> 顺序返回 <code>words</code> 中是其他单词的子字符串的所有单词。</p>\n",
    "\n",
    "<p>如果你可以删除 <code>words[j]</code>&nbsp;最左侧和/或最右侧的若干字符得到 <code>words[i]</code> ，那么字符串 <code>words[i]</code> 就是 <code>words[j]</code> 的一个子字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"mass\",\"as\",\"hero\",\"superhero\"]\n",
    "<strong>输出：</strong>[\"as\",\"hero\"]\n",
    "<strong>解释：</strong>\"as\" 是 \"mass\" 的子字符串，\"hero\" 是 \"superhero\" 的子字符串。\n",
    "[\"hero\",\"as\"] 也是有效的答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"leetcode\",\"et\",\"code\"]\n",
    "<strong>输出：</strong>[\"et\",\"code\"]\n",
    "<strong>解释：</strong>\"et\" 和 \"code\" 都是 \"leetcode\" 的子字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"blue\",\"green\",\"bu\"]\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 30</code></li>\n",
    "\t<li><code>words[i]</code> 仅包含小写英文字母。</li>\n",
    "\t<li>题目数据 <strong>保证</strong> 每个 <code>words[i]</code> 都是独一无二的。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [string-matching-in-an-array](https://leetcode.cn/problems/string-matching-in-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [string-matching-in-an-array](https://leetcode.cn/problems/string-matching-in-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"mass\",\"as\",\"hero\",\"superhero\"]', '[\"leetcode\",\"et\",\"code\"]', '[\"blue\",\"green\",\"bu\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        s = '#'.join(words)  # 将全部字符串连接成1个字符串s，每个字符串用#号分隔，\n",
    "                             # 避免错找\n",
    "        for w in words: # 遍历words\n",
    "            if s.count(w)>=2:res.append(w) # 利用count函数，在拼接后的s里面\n",
    "                                        #找到2次及以上，则符合题意，加入结果队列\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        for i,x in enumerate(words):\n",
    "            for j,y in enumerate(words):\n",
    "                if j != i and x in y:\n",
    "                    res.append(x)\n",
    "                    break\n",
    "                    \n",
    "\n",
    "       \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for i, x in enumerate(words):\n",
    "            for j, y in enumerate(words):\n",
    "                if j != i and x in y:\n",
    "                    ans.append(x)\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        s = ''\n",
    "        ans=[]\n",
    "        for i in words:\n",
    "            s += i+','\n",
    "        for i in words:\n",
    "            if s.count(i) >1:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for i, x in enumerate(words):\n",
    "            for j, y in enumerate(words):\n",
    "                if j != i and x in y:\n",
    "                    ans.append(x)\n",
    "                    break\n",
    "        return ans\n",
    "\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for i, wordi in enumerate(words):\n",
    "            for j, wordj in enumerate(words):\n",
    "                if i !=j and wordi in wordj:\n",
    "                    ans.append(wordi)\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for i, x in enumerate(words):\n",
    "            for j, y in enumerate(words):\n",
    "                if j != i and x in y:\n",
    "                    ans.append(x)\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        return [w for w in words if s.count(w)>1] if (s := \"#\".join(words)) else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        ans = list()\n",
    "        for word in words:\n",
    "            for w in words:\n",
    "                if len(word) >= len(w):\n",
    "                    continue\n",
    "                if w.find(word) >= 0:\n",
    "                    if word not in ans:\n",
    "                        ans.append(word)\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        n = len(words)\n",
    "        ans = set()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j and words[i] in words[j]:\n",
    "                    ans.add(words[i])\n",
    "        return list(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        ans = list()\n",
    "        for i, word in enumerate(words):\n",
    "            for j, w in enumerate(words):\n",
    "                if len(word) >= len(w):\n",
    "                    continue\n",
    "                if w.find(word) >= 0:\n",
    "                    if word not in ans:\n",
    "                        ans.append(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for i in words:\n",
    "            for j in words:\n",
    "                if i != j and i in j and i:\n",
    "                    ans.append(i)\n",
    "                    break\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "\n",
    "        @cache\n",
    "        def valied(s1, s2):\n",
    "            # m, n = len(s1), len(s2)\n",
    "            # if m > n:\n",
    "            #     return False\n",
    "            # i, j = 0, 0\n",
    "            # while i < m and j < n:\n",
    "            #     if s1[i] == s2[j]:\n",
    "            #         i += 1\n",
    "            #         j += 1\n",
    "            #     else:\n",
    "            #         j += 1\n",
    "            # return i == m\n",
    "            return w1 in w2\n",
    "        \n",
    "        result = list()\n",
    "        for w1 in words:\n",
    "            for w2 in words:\n",
    "                if w1 == w2:\n",
    "                    continue\n",
    "                # print(w1, w2, valied(w1, w2))\n",
    "                if valied(w1, w2):\n",
    "                    result.append(w1)\n",
    "                    break\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for i, x in enumerate(words):\n",
    "            for j, y in enumerate(words):\n",
    "                if j != i and x in y:\n",
    "                    ans.append(x)\n",
    "                    break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        words.sort(reverse=True, key=methodcaller('__len__'))\n",
    "        res = []\n",
    "        while words:\n",
    "            w = words.pop()\n",
    "            for w2 in words:\n",
    "                if w in w2:\n",
    "                    res.append(w)\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for i, x in enumerate(words):\n",
    "            for j, y in enumerate(words):\n",
    "                if j != i and x in y:\n",
    "                    ans.append(x)\n",
    "                    break\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=len)\n",
    "        ln = len(words)\n",
    "        ans = []\n",
    "        for i in range(ln):\n",
    "            for j in range(i + 1, ln):\n",
    "                if words[i] in words[j]:\n",
    "                    ans.append(words[i])\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        newList=[]\n",
    "        for i in range(len(words)):\n",
    "            for j in range(len(words)):\n",
    "                if i!=j and (words[i] in words[j]):\n",
    "                        newList.append(words[i])\n",
    "                        break\n",
    "        return newList"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def stringMatching(self, words):\n",
    "        \"\"\"\n",
    "        :type words: List[str]\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        als=','.join(words)\n",
    "        res=[]\n",
    "        for s in words:\n",
    "            if als.count(s)!=1:\n",
    "                res.append(s)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for i, x in enumerate(words):\n",
    "            for j, y in enumerate(words):\n",
    "                if j != i and x in y:\n",
    "                    ans.append(x)\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        list = []\n",
    "        count = len(words)\n",
    "        for i in range(count):\n",
    "            for j in range(count): \n",
    "                if words[i] == words[j]: continue\n",
    "\n",
    "                if words[j].find(words[i]) > -1 and words[i] not in list:\n",
    "                    list.append(words[i])\n",
    "\n",
    "        return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        # 暴力解法：先将字符串按长度排序，这样结果只能在数组前面的元素中，通过两个for循环求解\n",
    "        #只要前面的元素是后面某一个元素的子串，就break\n",
    "        result = [] \n",
    "        sorted_words = sorted(words, key=len)  \n",
    "        for i in range(len(sorted_words)-1):  \n",
    "            for j in range(i+1, len(sorted_words)):  \n",
    "                if sorted_words[i] in sorted_words[j]:  \n",
    "                    result.append(sorted_words[i]) \n",
    "                    break \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        count = defaultdict(int)\n",
    "        for ss in words:\n",
    "            count[ss] = len(ss)\n",
    "        item = sorted(count.items(), key=lambda e:e[1])\n",
    "        right = len(item) - 1\n",
    "        res = []\n",
    "        for i in range(len(item)):\n",
    "            for j in range(i+1, len(item)):\n",
    "                if item[i][0] in item[j][0]:\n",
    "                    res.append(item[i][0])\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        for i, a in enumerate(words):\n",
    "            for j, b in enumerate(words):\n",
    "                if i != j and a in b:\n",
    "                    res.append(a)\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        # ans = list()\n",
    "        # for word in words:\n",
    "        #     for w in words:\n",
    "        #         if len(word) >= len(w):\n",
    "        #             continue\n",
    "        #         if w.find(word) >= 0:\n",
    "        #             ans.append(word)\n",
    "        #             break\n",
    "        # return ans\n",
    "\n",
    "        return [w for w in words if s.count(w) > 1] if (s := \"$\".join(words)) else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        ans=[]\n",
    "        a=0\n",
    "        for i in words:\n",
    "            for j in words:\n",
    "                if len(i)<len(j):\n",
    "                    if self.is_sub(j,i) and i not in ans:\n",
    "                        ans.append(i)\n",
    "                elif len(j)<len(i):\n",
    "                    if self.is_sub(i,j) and j not in ans:\n",
    "                        ans.append(j)\n",
    "            a+=1\n",
    "        \n",
    "        return ans\n",
    "        # print(self.is_sub(\"mass\",\"as\"))\n",
    "    def is_sub(self, T: str, p: str):\n",
    "        n, m = len(T), len(p) \n",
    "        i, j = 0, 0                     # i 表示文本串 T 的当前位置，j 表示模式串 p 的当前位置\n",
    "        while i < n and j < m:          # i 或 j 其中一个到达尾部时停止搜索\n",
    "            if T[i] == p[j]:            # 如果相等，则继续进行下一个字符匹配\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                i = i - (j - 1)         # 如果匹配失败则将 i 移动到上次匹配开始位置的下一个位置\n",
    "                j = 0                   # 匹配失败 j 回退到模式串开始位置\n",
    "\n",
    "        if j == m:\n",
    "            return True             # 匹配成功，返回匹配的开始位置\n",
    "        else:  \n",
    "            return False\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def stringMatching(self, words):\n",
    "        \"\"\"\n",
    "        :type words: List[str]\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        als=','.join(words)\n",
    "        res=[]\n",
    "        for s in words:\n",
    "            if als.count(s)!=1:\n",
    "                res.append(s)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        res=[]\n",
    "        for w in range(len(words)):  #遍历words\n",
    "            t=words.pop(0)   # 弹出第1个字符串给t\n",
    "            for rest in words:  # 遍历剩余的words\n",
    "                if t in rest:   # 比较t是否为剩余字符串的子字符串\n",
    "                    res.append(t)  # 如果是，加入结果队列\n",
    "                    break # 不需再找，也避免找多了\n",
    "            words.append(t) # 将弹出第1个字符串加回队尾，准备下一个比较\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        for i in words:\n",
    "            for j in words:\n",
    "                if i in j and words.index(i)!=words.index(j):\n",
    "                    if i not in res:\n",
    "                        res.append(i)\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        res=[]\n",
    "        for i in words:\n",
    "            f=False\n",
    "            for j in words:\n",
    "                if i in j and i!=j:\n",
    "                    f=True\n",
    "                    break\n",
    "            if f==True:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=lambda x:len(x))\n",
    "        res = set()\n",
    "        for index, word in enumerate(words):\n",
    "            for i in range(index + 1, len(words)):\n",
    "                if word in words[i]:\n",
    "                    res.add(word)\n",
    "        return list(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "      ans =[]\n",
    "      for k,v in enumerate(words):\n",
    "        for k1,v1 in enumerate(words):\n",
    "          if k != k1 and v in v1:\n",
    "            ans.append(v)\n",
    "      return list(set(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "\n",
    "        # sliding window \n",
    "        # max window size is len(each word)-1\n",
    "        # ans =[]\n",
    "\n",
    "        # for each word, slice with sliding window, and check if sliced in the words list.\n",
    "        # if so, save to ans\n",
    "\n",
    "        min_len = min([len(it) for it in words])\n",
    "        ans = []\n",
    "\n",
    "        for item in words:\n",
    "            k = len(item)\n",
    "            for i in range(min_len,k):\n",
    "                for j in range(len(item) - min_len+1):\n",
    "                    sliced = item[j:j+i]\n",
    "                    if sliced in words and sliced not in ans:\n",
    "                        ans.append(sliced)\n",
    "        \n",
    "        return ans\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        \n",
    "        end=[]\n",
    "        num=len(words)\n",
    "        for i in range(num):\n",
    "            for j in range(num):\n",
    "                if i==j:\n",
    "                    continue\n",
    "                if words[i] in words[j]:\n",
    "                    end.append(words[i])\n",
    "                    break\n",
    "\n",
    "        return end\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        tmp = ','.join(words)\n",
    "        res = []\n",
    "        for word in words:\n",
    "            nums = tmp.count(word)\n",
    "            if nums >= 2:\n",
    "                res.append(word)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        ans = list()\n",
    "        for index, word in enumerate(words):\n",
    "            for string in words[:index] + words[index + 1:]:\n",
    "                if word in string:\n",
    "                    ans.append(word)\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        for i in range(len(words)):\n",
    "            for  j in range(i,len(words)):\n",
    "                if words[i] in words[j] and words[i] != words[j]:\n",
    "                    res.append(words[i])\n",
    "                if words[j] in words[i] and words[i] != words[j]:\n",
    "                    res.append(words[j])\n",
    "        return list(set(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\r\n",
    "        ans = list()\r\n",
    "        for i in range(len(words)):\r\n",
    "            for j in range(len(words)):\r\n",
    "                if words[i] != words[j] and words[j] in words[i] and words[j] not in ans:\r\n",
    "                    ans.append(words[j])\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        l, n = [], len(words)  # l是存储结果的列表\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j:  # 不是同一个字符串时\n",
    "                    if words[i] in words[j]:  # 判断是否是子字符串\n",
    "                        if words[i] not in l:  # 是子字符串时，判断是否在l列表中\n",
    "                            l.append(words[i])  # 不在列表中，添加进去\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        n = len(words)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j and words[i] in words[j] and words[i] not in ans:\n",
    "                    ans.append(words[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        ans = set()\n",
    "        for i in range(len(words)):\n",
    "            #for j in range(i + 1, len(words)):\n",
    "            for j in range(len(words)):\n",
    "                if words[i] == words[j]:\n",
    "                    continue\n",
    "                if words[i] in words[j]:\n",
    "                    ans.add(words[i])\n",
    "        return list(ans) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "\n",
    "        lis = set()\n",
    "        words.sort(key=lambda x : len(x))\n",
    "\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i+1, len(words)):\n",
    "                if len(words[i]) <= len(words[j]):\n",
    "                    if words[i] in words[j]:\n",
    "                        lis.add(words[i])\n",
    "        return list(lis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for i in words:\n",
    "            for j in words:\n",
    "                if j in i and j != i and j not in ans:\n",
    "                    ans.append(j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        # 暴力解法：先将字符串按长度排序，这样结果只能在数组前面的元素中，通过两个for循环求解\n",
    "        #只要前面的元素是后面某一个元素的子串，就break\n",
    "        result = [] \n",
    "        sorted_words = sorted(words, key=len)  \n",
    "        for i in range(len(sorted_words)-1):  \n",
    "            for j in range(i+1, len(sorted_words)):  \n",
    "                if sorted_words[i] in sorted_words[j]:  \n",
    "                    result.append(sorted_words[i]) \n",
    "                    break \n",
    "        return result\n",
    "   \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "      words.sort(key=len)\n",
    "      ans = []\n",
    "      for k,v in enumerate(words):\n",
    "        for j in words[k+1:]:\n",
    "          if v in j:\n",
    "            ans.append(v)\n",
    "      return list(set(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        res1=[]\n",
    "        res=[]\n",
    "        res2=[]\n",
    "        for i in words:\n",
    "            res1.append([i,len(i)])\n",
    "        print(res1)\n",
    "        words1=sorted(res1,key=lambda x:x[1])\n",
    "        print(words1)\n",
    "        for k in words1:\n",
    "            res2.append(k[0])\n",
    "        print(res2)\n",
    "        for i in range(len(res2)):\n",
    "            for j in range(i+1,len(res2)):\n",
    "                if res2[i] in res2[j]:\n",
    "                    res.append(res2[i])\n",
    "        print(list(set(res)))\n",
    "        return list(set(res))\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        for i ,x in enumerate(words):\n",
    "            for j ,y in enumerate(words):\n",
    "                if i != j  and  x in y :\n",
    "                    res.append(x)\n",
    "                    break \n",
    "        return res \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        hp, n, res, max, min  = [[] for _ in range(30)], len(words), [], 1, 29\n",
    "\n",
    "        for i in range(n):\n",
    "            index=len(words[i]) - 1\n",
    "            hp[index].append(words[i])\n",
    "            if max<index:\n",
    "                max=index\n",
    "            if min>index:\n",
    "                min=index\n",
    "\n",
    "        i1,i2,j1,j2,f = min,0,max,0,0\n",
    "           \n",
    "        while min<=i1<max:\n",
    "            while i2<len(hp[i1]):\n",
    "                while i1<j1<=max:\n",
    "                    while j2<len(hp[j1]):\n",
    "                        if hp[i1][i2] in hp[j1][j2]:\n",
    "                            res.append(hp[i1][i2])\n",
    "                            f=1\n",
    "                            break\n",
    "                        else:\n",
    "                            j2+=1\n",
    "                    j2=0        \n",
    "                    if f:\n",
    "                        break\n",
    "                    j1-=1                    \n",
    "                f=0\n",
    "                j1=max\n",
    "                i2+=1\n",
    "            i1+=1\n",
    "            i2=0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        tem = \",\".join(words)\n",
    "        for i in words:\n",
    "            cnt = tem.count(i)\n",
    "            if cnt >= 2:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        # ans = list()\n",
    "        # for word in words:\n",
    "        #     for w in words:\n",
    "        #         if len(word) >= len(w):\n",
    "        #             continue\n",
    "        #         if w.find(word) >= 0:\n",
    "        #             ans.append(word)\n",
    "        #             break\n",
    "        # return ans\n",
    "\n",
    "        return [w for w in words if s.count(w) > 1] if (s := \"$\".join(words)) else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for i in words:\n",
    "            for j in words:\n",
    "                if i != j and i in j and i not in ans:\n",
    "                    ans.append(i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        ans = ','.join(words)\n",
    "        res=[]\n",
    "        for s in words:\n",
    "            if ans.count(s)!=1:\n",
    "                res.append(s)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        list = [];\n",
    "        for k1,v1 in enumerate(words):\n",
    "            for k2,v2 in enumerate(words):\n",
    "                if k1 != k2 and v1 in v2:\n",
    "                    list.append(v1);\n",
    "                    break;\n",
    "\n",
    "        return list;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        als=','.join(words)\n",
    "        res=[]\n",
    "        for s in words:\n",
    "            if als.count(s)!=1:\n",
    "                res.append(s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "\n",
    "        ret = []\n",
    "        for x,word1 in enumerate(words):\n",
    "            for y,word2 in enumerate(words):\n",
    "                if x!=y and word1 in word2:\n",
    "                    ret.append(word1)\n",
    "                    break\n",
    "                    \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        def comp(s1, s2):\n",
    "            i1 = i2 = 0\n",
    "            n1 = len(s1)\n",
    "            n2 = len(s2)\n",
    "            while i1 != n1 and i2 != n2:\n",
    "                if s1[i1] == s2[i2]:\n",
    "                    i1 += 1\n",
    "                    i2 += 1\n",
    "                else:\n",
    "                    i2 += 1\n",
    "            return i1 == n1\n",
    "\n",
    "        ret = set()\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i + 1, len(words)):\n",
    "                s1 = words[i]\n",
    "                s2 = words[j]\n",
    "                if len(s1) > len(s2):\n",
    "                    s1, s2 = s2, s1\n",
    "                if s2.find(s1) != -1:\n",
    "                    ret.add(s1)\n",
    "        return list(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        res=[]\n",
    "        for i in range(len(words)):\n",
    "            for j in range(len(words)):\n",
    "                if i!=j and words[i] in words[j]:\n",
    "                    res.append(words[i])\n",
    "                    break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < len(words):\n",
    "            if words[j] in words[i] and words[j] not in res and i != j:\n",
    "                res.append(words[j])\n",
    "            \n",
    "            j += 1\n",
    "            if j >= len(words):\n",
    "                i += 1\n",
    "                j = 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        return [w for w in words if \" \".join(words).count(w)>1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        words = sorted(words,key = lambda x:len(x))\n",
    "        ans = []\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i+1,len(words)):\n",
    "                if words[i] in words[j]:\n",
    "                    ans.append(words[i])\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        # ans = list()\n",
    "        # for word in words:\n",
    "        #     for w in words:\n",
    "        #         if len(word) >= len(w):\n",
    "        #             continue\n",
    "        #         if w.find(word) >= 0:\n",
    "        #             ans.append(word)\n",
    "        #             break\n",
    "        # return ans\n",
    "\n",
    "        return [w for w in words if s.count(w) > 1] if (s := \"$\".join(words)) else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stringMatching(self, words: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        for i in words:\n",
    "            for j in words:\n",
    "                if i in j and len(i)<len(j) and i not in res:\n",
    "                    res.append(i)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
